package LK_Algorithm;

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
     TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}
public class Alg_Day_8 {
    /*合并二叉树
    * 如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
    * 解题思路:广度优先搜索-层序遍历-队列
    *         深度优先搜索-递归/栈*/
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }

    /*广度优先搜索*/
    public TreeNode mergeTrees1(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        //存放结果值
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //存放t1的值
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        //存放t2的值
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();

        queue.offer(merged);
        queue1.offer(t1);
        queue2.offer(t2);

        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
            /*为什么要写这一步呢,因为如果一个节点为空,那么你需要知道它的父节点,你保留了,left和right,那么在队列中的元素
            * 就可以当成他的父节点*/
            TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
           /*判断情况*/
            if (left1 != null || left2 != null) {

                if (left1 != null && left2 != null) {
                    TreeNode left = new TreeNode(left1.val + left2.val);
                    node.left = left;
                    queue.offer(left);
                    queue1.offer(left1);
                    queue2.offer(left2);
                } else if (left1 != null) {
                    node.left = left1;
                } else if (left2 != null) {
                    node.left = left2;
                }
            }
            if (right1 != null || right2 != null) {
                if (right1 != null && right2 != null) {
                    TreeNode right = new TreeNode(right1.val + right2.val);
                    node.right = right;
                    queue.offer(right);
                    queue1.offer(right1);
                    queue2.offer(right2);
                } else if (right1 != null) {
                    node.right = right1;
                } else {
                    node.right = right2;
                }
            }
        }
        return merged;
    }


    /*填充每个节点的下一个右侧节点指针
    * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
    * 解题思路:广度优先搜索-层序遍历-队列
    * 在层次遍历的过程中将我们将二叉树每一层的节点拿出来遍历并连接。*/
//    public Node connect(Node root) {
//        if (root == null) {
//            return root;
//        }
//        // 初始化队列同时将第一层节点加入队列中，即根节点
//        Queue<Node> queue = new LinkedList<Node>();
//        queue.add(root);
//        // 外层的 while 循环迭代的是层数
//        while (!queue.isEmpty()) {
//            // 记录当前队列大小
//            int size = queue.size();
//            // 遍历这一层的所有节点
//            for (int i = 0; i < size; i++) {
//                // 从队首取出元素
//                Node node = queue.poll();
//                // 连接
//                if (i < size - 1) {
//                    node.next = queue.peek();
//                }
//                // 拓展下一层节点
//                if (node.left != null) {
//                    queue.add(node.left);
//                }
//                if (node.right != null) {
//                    queue.add(node.right);
//                }
//            }
//        }
//        // 返回根节点
//        return root;
//    }






}
